package com.tgy.algorithm.base.other;

import java.util.Arrays;

public class _KMP_01 {

    public static int[] next(String pattern) {

        if (pattern == null || pattern.length() == 0) {
            return null;
        }

        int len = pattern.length();
        int[] next = new int[len];
        next[0] =  -1;

        int index = 2;
        int preIndex = 0;
        char[] chars = pattern.toCharArray();
        while (index < len) {
            if (chars[index - 1 ] == chars[preIndex]) {
                next[index++] = ++preIndex;
            }else if (preIndex == 0) {
                next[index++] = 0;
            }else {
                preIndex = next[preIndex];
            }
        }

        return next;
    }

    public static int kmp(String content,String pattern) {

        if (content == null || content.length() == 0 || pattern == null || pattern.length() == 0) {
            return -1;
        }
        int contentLen = content.length();
        int patternLen = pattern.length();
        if (patternLen > contentLen) {
            return -1;
        }

        int[] next = next(pattern);

        char[] contentChars = content.toCharArray();
        char[] patternChars = pattern.toCharArray();

        int preIndex = 0;
        int index = 0;

        while (index < contentLen && preIndex < patternLen) {
            if (contentChars[index] == patternChars[preIndex]) {
                index++;
                preIndex++;
            }else if (preIndex == 0) {
                // 从下一个开始
                index++;
            }else {
                // 跳转到前一个前缀与后缀一致的位置
                preIndex = next[preIndex];
            }
        }

        return preIndex >= patternLen ? index - preIndex:-1;
    }

    public static void main(String[] args) {
        String content = "aaabaacgh";
        String pattern = "abac";
        int[] nexts = next(pattern);
//        System.out.println(Arrays.toString(nexts));
        int index = kmp(content, pattern);
        System.out.println(index);
    }
}
